50 years in filesystems
linuxにおけるファイルシステムの50年間を追いかけるブログ連載
初期のシンプルなファイルシステムから見ていった方が技術の意図や差分が分かりやすい
dspinellis/unix-history-repoにunixの各時代のスナップショットがまとまってて便利
50 years in filesystems: 1974
ここではPDP-11 V7 Unix filesystemを扱う
ディスクはブロックのarrayとみなせる
ブロックの先頭にはsuperblockがある
今ならGUIDパーティションテーブルとかがある
mountシステムコールが最初にこれを読み込んで使う
inode
この時点の設定では1ブロック512byteで、そこに8inode入る、つまりinodeのサイズは1つ64byte
superblockに定義されているfreeなinodeの数はunsigned short型で持たれているので、ファイルはファイルシステムごとに65535個まで
1inodeにつき40bytesのaddr arrayなるものがあり、ここにdisk blockへの参照が13入る
The addr array contains 40 bytes, but it stores 13 disk block addresses, each using 3 bytes. This is good for 24 bits, or 16 megablocks of 512 bytes, each, for a total filesystem size of 8M kilobytes, or 8 GB.
ここではdisk block addressesが3bytesと言われているが、これはblock numberとも呼ばれている。ファイルシステムごとに固有の値である。
後に4, 8bytesとかになる
avashe.iconここの計算がよくわからないのだが、最大8GB対応しているらしい
13 (disk block addresses per inode) × 65534 (inode sizes per filesystem) ではどう考えても16 megablocksないので、何か見逃してる？
このころのディスクで8GBは相当大型
実際にはaddr arrayの10個は直接disk blockを指すもので、残り3つが間接的に指すもの
https://blog.koehntopp.info/uploads/1994/02/filestructure.gif
イメージとしてはこんな感じ
DBや検索システムにおけるインデックスみたいな構造
パフォーマンスを維持するためにはよく使うindirect blockはファイルシステムのバッファキャッシュにちゃんと載っていることが重要
ファイルへの書き込みは常にatomicに行われる
Durability(ファイル書き込み中のシステムクラッシュ時の整合性担保など)とかはここでは考えてない
DB開発者にとってはこの時点では不便だった
ファイルシステムの上位、下位構造
The lower filesystem is a sea of files. Files have no names, only numbers.
The upper filesystem uses a special type of file, with a simple 16-byte record structure, to assign a name of up to 14 characters to a file.
一緒に読んだ人曰く、1inodeに収まりきらないような大きさのファイルを複数のinodesで表そうとすると、名無しファイル(の断片)を指すinodeが大量にできる。それらがlower filesystem。それら下位構造を木構造でまとめていくと、どこかの高さで名前を与えられる(=私たちが考えるような実際のファイルやディレクトリのような単位と1:1対応した世界になる)。ここより上の世界がupper filesystem。
ファイル名にはスラッシュとnull文字以外は使える
ファイルシステムの利用にはファイル名から対応するinodeを検索する関数nameiを使う
探索したいパスのディレクトリはx permissionを持ってないと動作しない
パスの検索とパーミッションチェックの統合されたインターフェースという扱い
またここで取得されたファイルはロックされる
mountpointは特別なエントリーで、パス内で見つかるとそのファイルシステムのルートinodeに飛ばされるようになっている
これによりUnixは複数のファイルシステムがシステムに混じっていることをユーザに意識させないように努力している
指定されたパスのファイルやディレクトリに対応するinodeがない場合は、作成したり削除する機能もある
欠点
最大のサイズ
ファイル書き込みがatomicなためマルチプロセッシングのボトルネックとなることがある
nameiが線形に探索するのでディレクトリ320エントリ以上になると重たくなる
ファイルの強制ロックがなく、アドバイザリロックしかない
ファイルを即座に削除させるシステムコールがない
inodeへの参照がなくなったらガーベジコレクトされる
たとえばログを書き込むプロセスが適切にクローズしてないと、誰にも気づかれないままディスクスペースを圧迫し続ける
初期にはrmdir, mkdirがなく、レースコンディションを起こすことがあった
フラグメンテーションへの耐性がない
50 years in filesystems: 1984
4.3BSDのFast File Systemについて